home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / DRAWLINE.ZIP / DRAWLINE.DOC next >
Text File  |  1992-02-06  |  5KB  |  116 lines
  1. ─ (F) Zone 3 Pascal Programming (3:635/552@fidonet) ──────────────── Z3_PASCAL ─
  2.  Msg  : 77 of 90 - 67                                                           
  3.  From : Frank Malcolm               3:712/505               Sat 01 Feb 92 15:54 
  4.  To   : Ben Burns                                                               
  5.  Subj : Bresenham?                                                              
  6. ────────────────────────────────────────────────────────────────────────────────
  7. Ben, hi.
  8.  
  9.  BB>         a) What is Bresenham's line drawing algorithm?  If
  10.  BB>        someone would be willing to leave the algorithm here
  11.  BB>  it would be much apreciated. also
  12.  
  13. J. E. Bresenham wrote "Algorithm for Computer Control of a Digital Plotter"
  14. in the IBM Systems Journal in 1965 (yes, 1965!). It's described in most
  15. books on graphics programming and I believe it's still regarded as the
  16. fastest way to draw lines. Can also be adapted to other shapes. It seems to
  17. be the method used by Turbo Pascal, so you won't get any improvement by
  18. coding it yourself (but you'll learn heaps!)
  19.  
  20. Wilton's version in "Programmer's Guide to PC & PS/2 Video Systems" is
  21. separately optimised (different versions) for each of the different display
  22. modes, and looks for all the special cases (vertical, horizontal). It's
  23. fast.
  24.  
  25. A Pascal version appeared in APC in April '88 and very similarly in another
  26. book I've got. I'll post it here, but if you can get the original article
  27. the description is helpful for understanding.
  28.  
  29. procedure draw_line (xstart, ystart, xend, yend: integer);
  30.           { Bresenham's line-drawing algorithm. APC April '88. }
  31.           { See also Using Turbo & IBM Pascal p364, and Newman & Sproull }
  32. var x, y,          { current x and y coordinates }
  33.     d,             { decision variable }
  34.     a, b,          { line displacements in x and y }
  35.     dx_diag,       { diagonal x step for next pixel }
  36.     dy_diag,       { diagonal y step for next pixel }
  37.     dx_nondiag,    { non-diagonal x step for next pixel }
  38.     dy_nondiag,    { non-diagonal y step for next pixel }
  39.     diag_inc,      { d increment for diagonal steps }
  40.     nondiag_inc,   { d increment for non-diagonal steps }
  41.     swap,          { temporary variable for swaps }
  42.     i: integer;
  43. begin { draw_line }
  44. x := xstart;       { line starting point }
  45. y := ystart;
  46.  
  47. { Determine drawing direction and step to next pixel. }
  48. a := xend - xstart; { Calculate difference in x }
  49. b := yend - ystart; { Calculate difference in y }
  50. { Determine whether ending point lies to right or left of starting point. }
  51. if a < 0 then       { Drawing towards smaller x-values? }
  52.   begin             { Yes, because a is negative }
  53.   a := -a;          { Make a positive }
  54.   dx_diag := -1;    { and set x-movement accordingly }
  55.   end
  56. else                { Draw is towards larger x-values. }
  57.   dx_diag := 1;     { Set x-movement towards larger x. }
  58.  
  59. { Determine whether ending point lies above or below starting point. }
  60. if b < 0 then       { Drawing towards smaller y-values? }
  61.   begin             { Yes, because b is negative }
  62.   b := -b;          { Make b positive }
  63.   dy_diag := -1;    { and set y-movement accordingly }
  64.   end
  65. else
  66.   dy_diag := 1;     { Set y-movement towards larger y. }
  67.  
  68. { Identify octant containing ending point. }
  69. if a < b then       { Is y-difference larger than x-difference? }
  70.   begin             { Yes, so swap a and b }
  71.   swap := a;
  72.   a := b;
  73.   b := swap;
  74.   dx_nondiag := 0;  { Since y difference is larger, x doesn't change on }
  75.   dy_nondiag := dy_diag; { non-diagonal steps but y changes every step. }
  76.   end
  77. else
  78.   begin             { When x difference is larger than y difference, x }
  79.   dx_nondiag := dx_diag; { changes every step and y changes only on the }
  80.   dy_nondiag := 0;       { diagonal steps. }
  81.   end;
  82. d := b ++ b - a;    { Initial value for d is 2 * b - a. }
  83. nondiag_inc := b + b; { Set initial d increment values }
  84. diag_inc := b + b - a - a;
  85. for i := 0 to a do  { Draw the a + 1 pixels. }
  86.   begin
  87.   plot (x, y, 1);
  88.   if d < 0 then     { Is mid-point above the line? }
  89.     begin           { Yes, step non-diagonally. }
  90.     x := x + dx_nondiag;
  91.     y := y + dy_nondiag;
  92.     d := d + nondiag_inc; { Update the decision variable. }
  93.     end
  94.   else              { Mid-point is below the line, so step diagonally. }
  95.     begin
  96.     x := x + dx_diag;
  97.     y := y + dy_diag;
  98.     d := d + diag_inc; { Update the decision variable. }
  99.     end
  100.   end
  101. end { draw_line };
  102.  
  103.  
  104.  BB>         b) Would somebody be willing to lend me a copy of
  105.  BB>  `The programmers
  106.  BB> Guide to PC & PS/2 Video Systems'.. I dont have enough
  107.  BB> money to actually buy it
  108.  
  109. I have it, but use it frequently. Are you in Sydney?
  110.  
  111. Regards, FIM
  112.  
  113. --- via Silver Xpress V2.28 [NR]
  114.  * Origin: Sydney PC Users Group  COMPAQ BBS (3:712/505)
  115.  
  116.